1. Field of the Invention
The present invention is generally related to communication networks. More particularly, the present invention is related to systems and methods for interleaving data in communication devices.
2. Related Art
As in other communications systems, cable modem systems may be subject to intermittent, random bursts of noise, often referred to as burst noise or impulse noise. When such a noise burst occurs, it may introduce errors into packets of information transmitted over the system. In some cases, these errors may be corrected by Forward Error Correction (FEC). The ability of FEC to correct errors may be further enhanced through the use of interleaving. FEC is the ability of a receiving station to correct a transmission error in a data burst. To enable FEC, the transmitting station appends information to the data in the form of error correction bits. For example, Hamming codes provide for FEC using a “block parity” mechanism. Generally, use of the “block parity” may allow the correction of single bit errors and detection of two bit errors per unit of data. Other code types may be used to implement FEC as well.
For example, Reed Solomon (RS) error correction is another frequently used FEC error correction technique in which parity bits are added to a group of data bits to produce what is known as a codeword. Each codeword is capable of correcting only a certain number of data errors in the data represented by the codeword. For example, codeword A may be capable of correcting five data errors in the data represented by the codeword. If a particular noise burst occurs which causes eight data errors in the data, for example, only five data errors may be corrected by the Reed Solomon technique. Thus, three data errors in the data will remain.
In an attempt to extend the effectiveness of FEC error correction techniques such as Reed Solomon encoding, a codeword byte reordering process known as interleaving may be performed. Interleaving is a process of reordering symbols or bytes in a group of transmitted codewords such that adjacent symbols or bytes in the data stream are not from the same codeword. The interleaving process aids in reducing effects of burst errors (for example, multiple consecutive errors in data represented by a codeword) because rearranging the codeword symbols or bytes distributes the errors among multiple codewords. With further reference to the example above, the data represented by codeword A may also be represented by codeword B (that is, codeword A may represent a portion of the data, and codeword B may represent a portion of the data). Codewords A and B may be composed of ten bytes each.
Instead of transmitting the codewords in byte order such that the first byte of codeword A is followed by the second byte of codeword A, and so on, interleaving may be used to transmit the first byte of codeword A, followed by the first byte of codeword B, followed by the second byte of codeword A, followed by the second byte of codeword B, and so on, until all bytes of the codewords are transmitted.
In this scheme, if a noise burst occurs spanning eight codeword bytes, it will affect four bytes of codeword A and four bytes of codeword B. Thus, the maximum data errors capable of being corrected by the codewords will not likely be exceeded, and the effectiveness of the Reed Solomon technique is extended.
FIG. 1 illustrates a conventional system 100 for interleaving data in a communication device. For example, system 100 may be implemented in a conventional cable modem. Interleaving is typically employed with the use of two separate memory devices memory 115 and memory 120, as illustrated in FIG. 1. System 100 also comprises write module 105, which receives data from an encoder, such as an RS encoder, and alternately writes it in blocks to memory 115 and memory 120, and read module 110, which reads blocks of data alternately from memory 115 and memory 120 in an interleaved fashion.
In the conventional interleaver system 100, write module 105 and read module 110 are not permitted to read and write to the same memory device at the same time. Rather, while write module 105 writes a block to memory 115, read module 110 reads a block from memory 120. Similarly, while write module 105 writes a block to memory 120, read module 110 reads a block from memory 115. By alternating reads and writes in this fashion, the interleaver system of FIG. 1 ensures that the write module 105 will never overwrite data stored in memory that has not yet been read by read module 110.
This “ping pong” technique also avoids processing delays in a communication system where blocks are of a fixed size. In such a system, the time required for the write module 105 to write a block and the time required for the read module 110 to read a block will be known quantities. Consequently, alternating reads and writes to memories 115 and 120 may be synchronized such that the amount of time write module 105 has to wait for read module 110 to finish reading from memory in order to begin writing and, conversely, the amount of time that read module 110 has to wait for write module 105 to finish writing to memory in order to begin reading, may be minimized.
However, the above-described system may incur processing delays in a system where blocks may be of a variable size. For example, in such a system, write module 105 may be required to write a short block to memory 115 while read module 110 is reading a longer block from memory 120. In this case, the write module 105 will finish operating in advance of read module 110. As a result, write module 105 must remain idle until read module 110 has completed reading the longer block from memory 120. Alternatively, read module 110 may be required to read a short block from memory 115 while write module 105 is writing a longer block to memory 120. In this case, read module 110 will finish operating in advance of write module 105. Consequently, read module 110 must remain idle until write module 105 has finished writing the longer block to memory 120. When write module 105 or read module 110 are idled, system throughput as well as the efficiency of data transmission from the communication device is decreased.
Therefore, what is needed is a system and method for interleaving data that avoids unnecessary delays in a system that permits variable-sized blocks, thereby increasing system throughput and efficiency of data transmission.